home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / emerald / emrldsys.lha / Language / Compiler / map.c < prev    next >
C/C++ Source or Header  |  1990-08-16  |  6KB  |  285 lines
  1. /*
  2.  * @(#)map.c    1.2  3/18/87
  3.  */
  4. /* Copyright 1986 Norm Hutchinson.     May not be used for any         *
  5.  * purpose without written permission from the author.               */
  6.  
  7. #include "assert.h"
  8. #include "system.h"
  9. #include "map.h"
  10.  
  11. #define INITIALSIZE 4
  12.  
  13. #define HASH(key, map) (((key) ^ ((key) >> 4)) & map->maxIndex)
  14. static void CheckOutHashTable();
  15.  
  16. Map Map_Create()
  17. {
  18.   register int i;
  19.   register Map m;
  20.  
  21.   m = (Map) malloc(sizeof(MapRecord));
  22.   m->maxIndex = INITIALSIZE - 1;
  23.   m->maxCount = m->maxIndex - (m->maxIndex >> 2); /* Max fill 87.5 % */
  24.   m->count = 0;
  25.   m->table = (TEPtr) malloc(INITIALSIZE * sizeof(TE));
  26.   for (i = 0; i < INITIALSIZE; i++) {
  27.     m->table[i].key = NIL;
  28.   }
  29. #ifdef DEBUGMAP
  30.       CheckOutHashTable(m);
  31. #endif DEBUGMAP
  32.   return(m);
  33. }
  34.  
  35. Map Map_CreateSized(fCount)
  36. int fCount;
  37. {
  38.   register int i;
  39.   register Map m;
  40.  
  41.   assert(fCount > 0);
  42.   m = (Map) malloc(sizeof(MapRecord));
  43.   for (i = 1; i < fCount; i += i);
  44.   m->maxIndex = i - 1;
  45.   m->maxCount = m->maxIndex - (m->maxIndex >> 2); /* Max fill 87.5 % */
  46.   m->count = 0;
  47.   m->table = (TEPtr) malloc((unsigned)((m->maxIndex+1) * sizeof(TE)));
  48.   for (i = 0; i <= m->maxIndex ; i++) {
  49.     m->table[i].key = NIL;
  50.   }
  51. # ifdef lint
  52.   CheckOutHashTable(m);
  53. #endif  
  54. #ifdef DEBUGMAP
  55.   CheckOutHashTable(m);
  56. #endif DEBUGMAP
  57.   return(m);
  58. }
  59.  
  60. void Map_Destroy(m)
  61. register Map m;
  62. {
  63.   if (m == (Map) NULL) return;
  64. #ifdef DEBUGMAP
  65.   CheckOutHashTable(m);
  66. #endif DEBUGMAP
  67.   free((char *)m->table);
  68.   free((char *)m);
  69. }
  70.  
  71. static void ExpandHashTable(m)
  72. register Map m;
  73. {
  74.   register TE *nh, *oe, *ne;
  75.   register int oldHashTableSize = m->maxIndex + 1, i;
  76.   register int key;
  77.   int index;
  78.  
  79.   m->maxIndex = oldHashTableSize * 2 - 1;
  80.   m->maxCount = m->maxIndex - (m->maxIndex >> 2);
  81.   nh = (TEPtr) malloc((unsigned)(oldHashTableSize * 2 * sizeof(TE)));
  82.   for (i = 0; i <= m->maxIndex; i++) nh[i].key = NIL;
  83.   for (i = 0; i < oldHashTableSize; i++) {
  84.     oe = &m->table[i];
  85.     key = oe->key;
  86.     if (key == NIL) continue;
  87.     index = HASH(key, m);
  88.     while (1) {
  89.       ne = &nh[index];
  90.       if (ne->key == NIL) {
  91.     ne->key = oe->key;
  92.     ne->value = oe->value;
  93.     break;
  94.       } else {
  95.         assert(ne->key !=key);
  96.     index++;
  97.     if (index > m->maxIndex) index = 0;
  98.       }
  99.     }
  100.   }
  101.   free((char *)m->table);
  102.   m->table = nh;
  103. #ifdef DEBUGMAP
  104.   CheckOutHashTable(m);
  105. #endif DEBUGMAP
  106. }
  107.  
  108. int Map_Lookup(m, key)
  109. register Map m;
  110. register int key;
  111. {
  112.   register int index = HASH(key, m);
  113.   register TEPtr e;
  114.  
  115. #ifdef DEBUGMAP
  116.   CheckOutHashTable(m);
  117. #endif DEBUGMAP
  118.   while (1) {
  119.     e = &m->table[index];
  120.     if (e->key == NIL) {        /* we did not find it */
  121.       return (NIL);
  122.     } else if (e->key == key) {
  123.       return (e->value);
  124.     }
  125.     if (++index > m->maxIndex) index = 0;
  126.   }
  127. }
  128.  
  129. void Map_Delete(m, key)
  130. register Map m;
  131. register int key;
  132. /* Remove the entry, if it is there */
  133. {
  134.   register int index = HASH(key, m);
  135.   register int value;
  136.   register TEPtr e;
  137.  
  138.   while (1) {
  139.     e = &m->table[index];
  140.     if (e->key == NIL) {        /* we did not find it */
  141. #ifdef DEBUGMAP
  142.       CheckOutHashTable(m);
  143. #endif DEBUGMAP
  144.       return;
  145.     }
  146.     if (e->key == key) {
  147.       /* Found it, now remove it */
  148.       m->count--;
  149.       e->key = NIL;
  150.       e->value = NIL;
  151.       while (1) {
  152.         /* rehash until we reach nil again */
  153.         if (++index > m->maxIndex) index = 0;
  154.         e = & m->table[index];
  155.         key = e->key;
  156.         if (key == NIL) {
  157. #ifdef DEBUGMAP
  158.             CheckOutHashTable(m);
  159. #endif DEBUGMAP
  160.         return;
  161.     }
  162.         /* rehashing is done by removing then reinserting */
  163.         value = e->value;
  164.         e->key = e->value = NIL;
  165.         m->count--;
  166.         Map_Insert(m, key, value);
  167.       }
  168.     }
  169.     if (++index > m->maxIndex) index = 0;
  170.   }
  171. }
  172.  
  173. void Map_Insert(m, key, value)
  174. register Map m;
  175. register int key, value;
  176. {
  177.   register int index;
  178.   register TEPtr e;
  179.   assert(key != NIL);
  180.   if (m->count >= m->maxCount) ExpandHashTable(m);
  181.   index = HASH(key, m);
  182.   while (1) {
  183.     e = &m->table[index];
  184.     if (e->key == NIL) {        /* put it here */
  185.       e->key = key;
  186.       e->value = value;
  187.       m->count++;
  188. #ifdef DEBUGMAP
  189.       CheckOutHashTable(m);
  190. #endif DEBUGMAP
  191.       return;
  192.     } else if (e->key == key) {
  193.       e->value = value;
  194. #ifdef DEBUGMAP
  195.       CheckOutHashTable(m);
  196. #endif DEBUGMAP
  197.       return;
  198.     }
  199.     if (++index > m->maxIndex) index = 0;
  200.   }
  201. }
  202.  
  203. int Map_FindNext(m, startIndex, keyPtr, valuePtr)
  204. register Map m;
  205. int *startIndex;
  206. int *keyPtr, *valuePtr;
  207. {
  208.   register int i;
  209.   register TEPtr e;
  210.   for (i = *startIndex; i <= m->maxIndex; i++) {
  211.     e = &m->table[i];
  212.     if (e->key != NIL) {
  213.       *keyPtr = e->key;
  214.       *valuePtr = e->value;
  215.       *startIndex = i + 1;
  216.       return(1);
  217.     }
  218.   }
  219.   *keyPtr = NIL;
  220.   *valuePtr = NIL;
  221.   *startIndex = -1;
  222.   return(0);
  223. }
  224.  
  225. void Map_Print(m)
  226. register Map m;
  227. {
  228.     int key, value, index;
  229.     printf(
  230.         "\nDump of map @ 0x%05x, %d entr%s, current max %d\nIndex\tKey\t\tValue\n",
  231.     m, m->count, m->count == 1 ? "y" : "ies",  m->maxCount);
  232.     for (index = 0; index <= m->maxIndex; index++) {
  233.         key = m->table[index].key;
  234.         value = m->table[index].value;
  235.     printf("%3d\t0x%08.8x\t0x%08.8x\n", index, key, value);
  236.     }
  237. }
  238.  
  239. static void CheckOutHashTable(m)
  240. register Map m;
  241. {
  242.   register int i;
  243.   register TEPtr realElement, e;
  244.   register int index, firstIndex, count;
  245.   count = 0;
  246.  
  247.   for (i = 0; i <= m->maxIndex; i++) {
  248.     realElement = &m->table[i];
  249.     if (realElement->key != NIL) {
  250.       count++;
  251.       index = HASH(realElement->key, m);
  252.       firstIndex = index;
  253.       while (1) {
  254.     e = &m->table[index];
  255.     if (e->key == NIL) {        /* we did not find it */
  256.       break;
  257.     } else if (e->key == realElement->key) {
  258.       break;
  259.     } else {
  260.       index++;
  261.       if (index > m->maxIndex) index = 0;
  262.       if (index == firstIndex) {
  263.         index = -1;
  264.         break;
  265.       }
  266.     }
  267.       }
  268.       
  269.       if (index == -1 || e->key != realElement->key) {
  270.       fprintf(stderr,
  271.         "Map problem: Key 0x%x, rightIndex %d, realIndex %d value 0x%x\n",
  272.         realElement->key, firstIndex, index, realElement->value);
  273.           Map_Print(m);
  274.       }
  275.     }
  276.   }  
  277.   if (count != m->count) {
  278.     fprintf(stderr,
  279.       "Map problem: Should have %d entries, but found %d.\n", m->count,
  280.       count);
  281.     Map_Print(m);
  282.   }
  283. }
  284.  
  285.